The use of unmanned platforms is advantageous in many situations, both military and civilian. In order for such a platform to be truly useful, it is desirable to offer the platform autonomous navigational capability, as otherwise, continuous communication between a remote operator and the platform would be required. Without continuous control or autonomous navigation capability, the platform may collide with obstacles that were not previously known, endangering both the platform and others in the vicinity. A maneuverable platform may be assigned a mission that includes one or more tasks that it is to accomplish. Such tasks may include, for example, traveling to a defined location, or waypoint, and performing a defined activity at the location, or be a loosely defined task such as to patrol an area. The route traveled must be selected such as to avoid obstacles and restricted zones. Such obstacles may be fixed, or may be moving. Since the positions of moving obstacles, such as other platforms, may be constantly changing, an autonomous platform should preferably be capable of detecting such obstacles, estimating their anticipated routes, and maneuvering in such a manner as to avoid a collision. Therefore, in order to complete a task in the absence of continuous guidance from a human operator, a platform should preferably be able to perform autonomously such functions as navigation, conforming to a timetable, selecting a route to avoid known fixed obstacles or other forbidden areas, detecting the locations and courses of obstacles and other platforms, and conforming to defined rules such as traffic regulations.
In particular, such considerations apply to an unmanned surface vehicle (USV) operating at sea, or an unmanned aerial vehicle (UAV). For the sake of brevity a USV is considered, but this should not be regarded as limiting the scope of the present invention. A USV, in order to prevent collisions with other surface craft, should preferably be able to detect obstacles and other vessels, determine the speed and course of other vessels, and adjust its own motion (course and speed) in order to avoid a collision. In maneuvering to avoid a collision, a seagoing USV should preferably also conform to the International Regulations for Preventing Collisions at Sea (COLREGS). COLREGS determine the proper action to avoid collision when seagoing vessels encounter one another. COLREGS determine, depending on the types of the encountering vessels and the activities in which the vessels are engaged, among other considerations, how each vessel is expected to maneuver in order to avoid a collision. However, under some circumstances, COLREGS may be ambiguous. For example when more than two vessels are involved, several regulations may apply simultaneously, each prescribing a different, sometimes contradicting, action. In such situations, a vessel operator is expected to employ judgment and common sense in implementing COLREGS so as to best avoid a collision. For this reason, COLREGS are difficult to assimilate in programming for an autonomous USV.
Michael R. Benjamin (“Interval Programming: A Multi-Objective Optimization Model for Autonomous Vehicle Control”, Doctoral thesis, Brown University, 2002) describes a method for autonomously controlling a vehicle using piecewise-defined interval programming (IvP) behavior functions. The IvP functions are piecewise defined such that each point in the decision space is covered by one and only one piece, and each piece is an interval programming piece. The decision variables might be, for example, course and speed. The behavior functions are typically an approximation of a behavior's true underlying utility function. According to the multi-objective optimization method described in U.S. Pat. No. 7,139,741 (Benjamin), an IvP function is set up for each individual behavior of the vehicle in each step. For example, when the COLREGS rules are considered, an IvP function will be defined for each rule in each step. About 600 linear pieces are used to represent the waypoint behavior (reaching a waypoint) (“Navigation of Unmanned Marine Vehicles in Accordance with the Rules of The Road”, Benjamin et al, May 2006). The interval programming problem consists of a set of k piecewise-defined objective functions. Each objective function (1 . . . k), defined over n decision variables has an associated weight. A solution to the interval programming problem is the single decision with the highest value, when evaluated by w1×f1(x1, . . . xn)+ . . . wk×fk(x1, . . . xn). Typically, adding the weighted piecewise functions will not create another piecewise defined function because the pieces of all IvP functions do not overlap. The intersection is done using the upper and lower bounds of each dimension of the pieces, such that a new piece is formed at the intersection of the two pieces. The combinations of the objectives can be represented in a tree, with k+1 layers, where k is the number of the objective functions. Each layer 1 (1=2, . . . , k+1) in the tree represents all possible pieces of the objective 1-1 for each piece at the parent layer. If, for example, we have 5 objectives with 600 pieces each, the tree will hold 6005+1 nodes. There are many possible algorithms to search through the tree. One known algorithm is “Branch and Bound”. In U.S. Pat. No. 7,139,741 by Benjamin, Michael R. a method using grid structures is taught. As the IvP function should be formulated in regard to each obstacle and due to the plurality and numerousness of constraints, in real world navigation problems, the proposed method may become unwieldy.
Other groups have described methods for autonomous navigation of a land vehicle, where the motion of vehicles is limited to predetermined roads or courses. Such methods plot out an optimum course in advance, making adjustments in response to obstacles. Such methods are not suitable for navigation in such situations as on the open sea, where vehicles may be free to travel in almost any direction.
It is an object of the present invention to provide an effective and flexible autonomous navigation system and method for a maneuverable unmanned platform that enables the platform to accomplish a mission while avoiding collisions or too close encounters with obstacles and abiding traffic regulations.
Other aims and advantages of the present invention will become apparent after reading the present invention and reviewing the accompanying drawings.